package Leetcode.图;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/9/6 22:17
 * @Description: 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
 *
 *  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
 *
 * 输入：graph = [[1,2],[3],[3],[]]
 * 输出：[[0,1,3],[0,2,3]]
 * 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
 * 示例 2：
 *
 *
 *
 * 输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
 * 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
 *
 *
 * 提示：
 *
 * n == graph.length
 * 2 <= n <= 15
 * 0 <= graph[i][j] < n
 * graph[i][j] != i（即不存在自环）
 * graph[i] 中的所有元素 互不相同
 * 保证输入为 有向无环图（DAG）
 */

public class 所有可能的路径 {
    /**
     *  dfs比较好做
     *  bfs的话不符合题意
     * @param graph graph就是一个邻接表
     * @return  所有可能的路径
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        //顶点数
        int vertexCount = graph.length;
        //有向无环图无需visited数组
        //第一个节点开始
        path.add(0);
        //后续vertexCount表示的是graph的索引，所以传入 -1
        dfs(graph, 0, vertexCount - 1, ans, path);
        return ans;
    }

    private void dfs(int[][] graph, int i, int vertexCount,
                     List<List<Integer>> ans, List<Integer> path) {
        //当前顶点为最后一个顶点  路径+1
        if (i == vertexCount) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int y : graph[i]) {
            path.add(y);
            dfs(graph, y, vertexCount, ans, path);
            //回溯，删除最后一个元素
            path.remove(path.size() - 1);
        }

    }
}
